#include "string.h"
#include <algorithm>
#include <cassert>
#include <csignal>
#include <cstddef>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <stdexcept>
std::ostream &operator<<(std::ostream &cout, const string &s)
{
    for (size_t i = 0; i < s.size_; i++)
    {
        cout << s[i];
    }
    return cout;
}
std::istream &operator>>(std::istream &cin, string &str)
{
    str.clear();
    char ch = cin.get();
    while (ch != ' ' && ch != '\n')
    {
        str += ch;
        ch = cin.get();
    }
    return cin;
}
string::string(const string &str)
{
    this->str_ = new char[str.capacity_ + 1];
    memcpy(this->str_, str.str_, str.size_ + 1);
    this->size_ = str.size_;
    this->capacity_ = str.capacity_;
}
string::string(const string &str, size_t pos, size_t len)
{
    if (pos > str.size_)
        throw std::out_of_range("string::string: position out of range");
    size_t actual_len = len;
    if (pos + len > str.size_ || len == npos)
        actual_len = str.size_ - pos;

    this->size_ = actual_len;
    this->capacity_ = this->size_;
    this->str_ = new char[this->capacity_ + 1];
    memcpy((*this).str_, str.str_ + pos, actual_len);
    this->str_[this->size_] = '\0';
}
string::string(const char *str)
{
    if (!str)
    {
        this->size_ = this->capacity_ = 0;
        this->str_ = new char[1];
        this->str_[0] = '\0';
    }
    else
    {
        this->size_ = strlen(str);
        this->capacity_ = this->size_;
        this->str_ = new char[this->size_ + 1];
        memcpy(this->str_, str, this->size_ + 1);
    }
}
string::string(const char *str, size_t n)
{
    this->size_ = n;
    this->capacity_ = this->size_;
    this->str_ = new char[this->size_ + 1];
    memcpy(this->str_, str, this->size_);
    this->str_[this->size_] = '\0';
}
string::string(size_t n, char c)
{
    this->size_ = n;
    this->capacity_ = this->size_;
    this->str_ = new char[this->size_ + 1];
    memset(this->str_, c, n);
    this->str_[this->size_] = '\0';
}
void string::push_back(char c)
{
    if (this->size_ + 1 > this->capacity_)
    {
        size_t newCapacity = this->capacity_ == 0 ? 4 : this->capacity_ * 2;
        char *str = new char[newCapacity];
        if (str)
            memcpy(str, this->str_, this->size_);
        delete[] this->str_;
        this->str_ = str;
        this->capacity_ = newCapacity;
    }
    this->str_[size_++] = c;
    this->str_[this->size_] = '\0';
}
string &string::operator+=(char c)
{
    push_back(c);
    return *this;
}
const char *string::data() const
{
    return this->str_;
}
void string::append(const char *str)
{
    assert(str);
    size_t len = strlen(str);
    if (this->size_ + len > this->capacity_)
    {
        size_t newCapacity = 2 * this->capacity_ > this->size_ + len ? 2 * this->capacity_
                                                                     : this->size_ + len;
        reserve(newCapacity);
    }
    memcpy(this->str_ + this->size_, str, len + 1);
    this->size_ += len;
    this->str_[this->size_] = '\0';
}
void string::append(const string &str)
{
    size_t len = str.size();
    if (this->size_ + len > this->capacity_)
    {
        size_t newCapacity = 2 * this->capacity_ > this->size_ + len ? 2 * this->capacity_
                                                                     : this->size_ + len;
        reserve(newCapacity);
    }
    memcpy(this->str_ + this->size_, str.data(), len);
    this->size_ += len;
    this->str_[this->size_] = '\0';
}
void string::append(const char *s, size_t n)
{
    assert(s);
    if (this->size_ + n > this->capacity_)
    {
        size_t newCapacity = 2 * this->capacity_ > n + this->size_ ? 2 * this->capacity_
                                                                   : this->size_ + n;
        reserve(newCapacity);
    }
    memcpy(this->str_ + this->size_, s, n);
    this->size_ += n;
    this->str_[this->size_] = '\0';
}
void string::append(size_t n, char c)
{
    if (this->size_ + n > this->capacity_)
    {
        size_t newCapacity = 2 * this->capacity_ > this->size_ + n ? 2 * this->capacity_
                                                                   : this->size_ + n;
        reserve(newCapacity);
    }
    memset(this->str_ + this->size_, c, n);
    this->size_ += n;
    this->str_[this->size_] = '\0';
}
void string::reserve(size_t n)
{
    if (n > this->capacity_)
    {
        char *str = new char[n + 1];
        if (this->str_ != nullptr)
            memcpy(str, this->str_, this->size_ + 1);
        else
            str[0] = '\0';
        delete[] this->str_;
        this->str_ = str;
        this->capacity_ = n;
    }
}
string &string::operator+=(const char *str)
{
    append(str);
    return *this;
}
char &string::operator[](size_t index)
{
    assert(index < this->size_);
    return this->str_[index];
}
const char &string::operator[](size_t index) const
{
    assert(index < this->size_);
    return this->str_[index];
}
bool string::operator<(const string &s) const
{
    size_t len = std::min(this->size_, s.size_);
    for (size_t i = 0; i < s.size(); i++)
    {
        if (this->str_[i] < s[i])
            return true;
        if (this->str_[i] > s[i])
            return false;
    }
    return this->size_ < s.size_;
}
bool string::operator<=(const string &s) const
{
    return *this < s || *this == s;
}
bool string::operator>(const string &s) const
{
    return !(*this <= s);
}
bool string::operator>=(const string &s) const
{
    return !(*this < s);
}
bool string::operator==(const string &s) const
{
    if (this->size_ != s.size_)
        return false;
    for (size_t i = 0; i < this->size_; i++)
        if (this->str_[i] != s[i])
            return false;
    return true;
}
bool string::operator!=(const string &s) const
{
    return !(s == *this);
}
string &string::operator=(const string &str)
{
    if (*this != str)
    {
        string tmp(str);
        this->swap(tmp);
    }
    return *this;
}
string &string::operator=(const char *str)
{
    if (!str)
        this->clear();
    else
    {
        size_t len = strlen(str);
        if (len > this->capacity_)
        {
            delete[] this->str_;
            this->str_ = new char[len + 1];
            this->capacity_ = len;
        }
        memcpy(this->str_, str, len + 1);
        this->size_ = len;
    }
    return *this;
}
string &string::operator=(char c)
{
    if (1 > this->capacity_)
    {
        delete[] this->str_;
        this->str_ = new char[2];
        this->capacity_ = 1;
    }
    this->str_[0] = c;
    this->str_[1] = '\0';
    this->size_ = 1;
    return *this;
}
void string::resize(size_t n, char c)
{
    if (n > this->size())
    {
        if (n > this->capacity_)
            reserve(n);
        for (size_t i = this->size_; i < n; i++)
            this->str_[i] = c;
    }
    this->size_ = n;
    this->str_[this->size_] = '\0';
}
void string::pop_back()
{
    assert(this->size_ != 0 && this->str_ != nullptr);
    this->str_[--this->size_] = '\0';
}
size_t string::size() const
{
    return this->size_;
}
size_t string::capacity() const
{
    return this->capacity_;
}
bool string::empty() const
{
    return this->size_ == 0;
}
void string::clear()
{
    this->str_[0] = '\0';
    this->size_ = 0;
}
string &string::insert(size_t pos, const string &str)
{
    assert(pos <= this->size_);
    size_t len = str.size();
    if (this->size_ + len > this->capacity_)
        reserve(2 * this->capacity_ > this->size_ + len ? 2 * this->capacity_ : this->size_ + len);
    memmove(this->str_ + pos + len, this->str_ + pos, this->size_ - pos);
    memcpy(this->str_ + pos, str.c_str(), len);    
    this->size_ += len;
    this->str_[this->size_] = '\0';
    return *this;
}
string &string::insert(size_t pos, const char *str)
{
    assert(pos <= this->size_);
    size_t len = strlen(str);
    if (this->size_ + len > this->capacity_)
        reserve(2 * this->capacity_ > this->size_ + len ? 2 * this->capacity_ : this->size_ + len);
    this->size_ += len;
    for (size_t i = this->size_; i > pos; i--)
        this->str_[i] = this->str_[i - len];
    for (size_t i = pos, j = 0; i < pos + len; i++)
        this->str_[i] = str[j++];
    this->str_[this->size_] = '\0';
    return *this;
}
string &string::erase(size_t pos, size_t len)
{
    assert(pos <= this->size_);
    if (pos + len >= this->size_)
    {
        this->str_[pos] = '\0';
        return *this;
    }
    memmove(this->str_ + pos, this->str_ + pos + len, this->size_ - pos - len + 1);
    this->size_ -= len;
    return *this;
}
string string::substr(size_t pos, size_t len) const
{
    if (len == npos || len >= this->size_ - pos)
        len = this->size_ - pos;
    string ret;
    ret.reserve(len);
    for (size_t i = 0; i < len; i++)
        ret += this->str_[pos + i];
    return ret;
}
const char *string::c_str() const
{
    return this->str_;
}
void string::swap(string &s)
{
    std::swap(s.str_, this->str_);
    std::swap(s.size_, this->size_);
    std::swap(s.capacity_, this->capacity_);
}
size_t string::find(const char *s, size_t pos) const
{
    const char *p = strstr(this->str_ + pos, s);
    if (p == nullptr)
        return npos;
    else
        return p - this->str_;
}
size_t string::find(char c, size_t pos) const
{
    for (size_t i = pos; i < this->size_; i++)
    {
        if (this->str_[i] == c)
            return i;
    }
    return npos;
}
string::~string()
{
    delete[] str_;
    this->str_ = nullptr;
    this->capacity_ = this->size_ = 0;
}
